package org.example.myleet.segmenttree;

public class DynamicSplitSegmentTree implements SegmentTree {
    private final Segment root;

    /**
     * 定义线段树控制的范围
     * @param leftBorder 范围的左端点
     * @param rightBorder 范围的右端点
     */
    public DynamicSplitSegmentTree(int leftBorder, int rightBorder) {
        root = new Segment(leftBorder, rightBorder);
    }

    @Override
    public void modify(int l, int r, int v, Segment segment) {
        if (l > r) {
            return;
        }
        if (null == segment) {
            segment = root;
        }
        if (l <= segment.l && segment.r <= r) {
            //更新的范围覆盖了整个线段，则直接修改线段的值，并标记add标签
            segment.v = v;
            segment.add = v;
            return;
        }
        //更新的范围没有覆盖到整个线段，此时需要根据更新范围对应更新线段的左节点和右节点的值
        pushDown(segment);
        if (l <= segment.mid) {
            //更新范围覆盖到左节点，修改左节点的值
            modify(l, r, v, segment.left);
        }
        if (r > segment.mid) {
            //更新范围覆盖到右节点，修改左右点的值
            modify(l, r, v, segment.right);
        }
        //根据左节点和右节点的值更新本范围内的值
        pushUp(segment);
    }

    /**
     * 查询区间中的最大值
     */
    @Override
    public int query(int l, int r, Segment segment) {
        if (l > r) {
            return 0;
        }
        if (null == segment) {
            segment = root;
        }
        if (l <= segment.l && segment.r <= r) {
            //查询的范围覆盖了整个线段，则查询结果为线段的值
            return segment.v;
        }
        //查询的范围没有覆盖到整个线段，此时需要根据线段的左节点和右节点的值确定查询范围的结果
        pushDown(segment);
        int v = 0;
        if (l <= segment.mid) {
            //查询范围覆盖到左节点
            v = Math.max(v, query(l, r, segment.left));
        }
        if (r > segment.mid) {
            //查询范围覆盖到右节点
            v = Math.max(v, query(l, r, segment.right));
        }
        return v;
    }

    @Override
    public void pushDown(Segment segment) {
        if (segment.l == segment.r) {
            //已经是叶子节点，无需继续劈开范围
            return;
        }
        if (null == segment.left) {
            segment.left = new Segment(segment.l, segment.mid);
        }
        if (null == segment.right) {
            segment.right = new Segment(segment.mid + 1, segment.r);
        }
        if (0 != segment.add) {
            //存在线段范围内的值需要更新，则传递到子节点上
            segment.left.v = segment.add;
            segment.right.v = segment.add;
            segment.left.add = segment.add;
            segment.right.add = segment.add;
            //传递完成，线段的值更新标签归零
            segment.add = 0;
        }
    }

    @Override
    public void pushUp(Segment segment) {
        //根据题意，线段的值取线段范围内的最大值
        segment.v = Math.max(segment.left.v, segment.right.v);
    }
}
